View Javadoc
   /***
    * ControlFlowGraph
    *
    * This is a class which represents a ControlFlowGraph.
    *
    * It subclasses the Graph from org/apache/commons/graph
    * and stores things such as the MethodGen object.
    */
   
  package junit.quilt.cover.generic;
  
  import junit.quilt.exception.QuiltException;
  
  import org.apache.bcel.*;
  import org.apache.bcel.generic.*;
  import org.apache.bcel.classfile.*;
  
  import org.apache.commons.graph.*;
  import org.apache.commons.graph.algorithm.search.*;
  import org.apache.commons.graph.domain.basic.*;
  
  import java.util.*;
  
  public class ControlFlowGraph
    extends DirectedGraphImpl
    implements DirectedGraph
  {
      private ClassGen clazz = null;
      private MethodGen method = null;
      private Method oldMethod = null;
      private ConstantPoolGen pool = null;
      private BlockVertex start = null;
      private BlockVertex end = null;
      
      private Map jsrEdges = new HashMap(); // JSR Edge/Edge
  
      /***
       * This constructs an empty ControlFlowGraph
       * for the current class.
       *
       * You need to call "initialize()" before the
       * graph is valid.
       */
      public ControlFlowGraph(InstContext context,
  			    MethodGen method)
      {
  	super( );
  	this.clazz = context.getClassGen();
  	this.method = method;
  	this.oldMethod = method.getMethod();
  	this.pool = context.getConstantPoolGen();
      }
  
      public void initialize( EdgeFactory factory ) {
  	SortedMap blocks = findBlocks( factory, method, pool );    // Position X Block Vertex
  	
  	// Simple Setup
  	LocalVariableTable lvt =    // Local Variable definitions.
  	    method.getLocalVariableTable( pool );
  	
  	setStartVertex( factory.makeStartVertex() );
  	setEndVertex( factory.makeEndVertex() );
  	
  	// This is to make sure our vertex is attached to
  	// the right entry point.
  	
  	BlockVertex first = (BlockVertex) blocks.get( blocks.firstKey() );
  	
  	addEdge( factory.makeNormalEdge( getStartVertex(),
  					 first ),
  		 getStartVertex(),
  		 first);
  	
  	
  	// Now, we iterate over all of the blocks, and set up their
  	// edges. . .
  
  	Iterator allBlocks = blocks.values().iterator();
  	while (allBlocks.hasNext()) {
  	  BlockVertex vertex = (BlockVertex) allBlocks.next();
  	  InstructionHandle last = vertex.getLastInst();
  	  InstructionHandle next = last.getNext();
  	  
  	  if (last.getInstruction() instanceof ReturnInstruction) {
  	    FlowControlEdge rEdge = factory.makeReturnEdge( vertex );
  	    addEdge( rEdge, vertex, getEndVertex() );
  	    
  	  } else if (last.getInstruction() instanceof RET) {
  	      // RET - End of the line for a Subroutine.
  	      // We do nothing to handle this.
  	  } else if (last.getInstruction() instanceof Select) {
  	    handleSelect( factory, next, last, vertex, blocks, lvt );
  	  } else if (last.getInstruction() instanceof IfInstruction) {
  	    handleIf( factory, next, last, vertex, blocks, lvt );
  	  } else if (last.getInstruction() instanceof GotoInstruction) {
  	    handleGoto( factory, next, last, vertex, blocks, lvt );
  	  } else if (last.getInstruction() instanceof JsrInstruction) {
  	    handleJSR( factory, next, last, vertex, blocks, lvt );
  	  } else if (last.getInstruction() instanceof ExceptionThrower) {
 	    handleExceptionThrower( factory, next, last, 
 				    vertex, blocks, lvt );
 	  } else {
 	    handleNormal( factory, next, last, vertex, blocks, lvt );
 	  }
 	}
 
 	Iterator jsrs = jsrEdges.keySet().iterator();
 	while (jsrs.hasNext()) {
 	    FlowControlEdge jEdge = // JSR Edge
 		(FlowControlEdge) jsrs.next();
 	    FlowControlEdge nEdge = // "Normal" Edge
 		(FlowControlEdge) jsrEdges.get( jEdge );
 
 	    BlockVertex jsrInst = // This is where we enter.
 		(BlockVertex) getSource( jEdge );
 	    BlockVertex start = // Where we start inlining
 		(BlockVertex) getTarget( jEdge );
 	    BlockVertex target = // When we find a RET, where to direct it to.
 		(BlockVertex) getTarget( nEdge );
 
 	    JSRInliner inliner = new JSRInliner( factory, target );
 
 	    DFS dfs = new DFS();
 	    dfs.visit( this, start, inliner ); // A miracle occours
 	    
 	    // At this point, the Subroutine has been copied
 	    //
 	    // The RET instructions in the copied routine have been
 	    // changed to NormalEdges pointing to the target of
 	    // the normal edge which will disappear real soon.
 	    //
 	    // getRoot() of the inliner, will return the copy of
 	    // the JSR Target we started the graph with.
 	    //
 	    
 	    removeEdge( jEdge );
 	    removeEdge( nEdge );
 	    addEdge( factory.makeNormalEdge( jsrInst, inliner.getRoot() ),
 		     jsrInst, inliner.getRoot());
 	    if (jsrInst.getLastInst().getInstruction() instanceof RET) {
 		jsrInst.chomp();
 	    }
 	}
     }
 
     /***
      * Returns a map between the Position
      * of an Instruction, and the BlockVertex
      * which contains it.
      *
      * It uses the method and pool to initialize
      * everything.
      *
      * @param method The method the graph is representing.
      * @param pool The constant pool.
      */
 
     private SortedMap findBlocks( EdgeFactory factory,
 				  MethodGen method,
 				  ConstantPoolGen pool )
     {
 	InstructionList iList = method.getInstructionList();
 	LineNumberTable lines = method.getLineNumberTable( pool );
 	
 	InstructionHandle inst[] = iList.getInstructionHandles();
 	SortedMap RC = new TreeMap();
 	
 	BlockVertex block = null;
 
 	boolean startNewBlock = true;
 
 	int lastStart = 0;
 	int i = 0;
 	while (i < inst.length) {
 	    // If the block is targeted by anything other than
 	    // the previous instruction, we need to put it on
 	    // a new block.
 	    
 	    if (hasInbound( inst[i] )) {
 		startNewBlock = true;
 	    }
 	    
 	    if (startNewBlock) {
 		lastStart = i;
 		startNewBlock = false;
 		
 		if (block != null) {
 		    addVertex( block );
 		    RC.put( new Integer( block.getPCStart() ), block );
 		}
 
 		block = factory.makeBlockVertex( lines );
 	    }
 	    
 	    block.addInstruction( inst[i] );
 	    
 	    if (hasOutbound( inst[i] )) {
 		startNewBlock = true;
 	    }
 	    i++;
 	}
 	if (block.length() > 0) {
 	    addVertex( block );
 	    RC.put( new Integer( block.getPCStart() ), block );
 	}
 
 	return RC;
     }
     
     /***
      * Given an InstructionHandle, it builds up a String
      * representing what comprises the top element
      * of the stack.
      *
      * It works, by looking at the stack backwards
      *
      * @param handle is the handle we want to find the
      * stack value for.
      *
      * @param locals is a LocalVariableTable which is
      * used for looking up the name of a variable.
      */
     public String getStackContents( InstructionHandle handle,
 				    LocalVariableTable locals )
     {
 	Instruction inst = handle.getInstruction();
 
 	if (hasInbound( handle )) {
 	    return "???";
 	}
 
 	if (inst instanceof LoadInstruction) {
 	    int index = ((LoadInstruction) inst).getIndex();
 	    return locals.getLocalVariable(index).getName();
 	}
 
 	return "???";
     }
 
     private BlockVertex lookup( Map vertices, int position ) 
     {
 	if (!vertices.containsKey( new Integer( position )))
 	    System.err.println("WARNING!  Tried to get non existant block!");
 
 	return (BlockVertex) vertices.get( new Integer( position ) );
     }
 
     private BlockVertex lookup( Map vertices, InstructionHandle ih )
     {
 	if (!vertices.containsKey( new Integer( ih.getPosition() )))
 	    System.err.println("WARNING!  Tried to get non existant block!");
 
 	return (BlockVertex) vertices.get( new Integer( ih.getPosition() ));
     }
 
     private boolean isCatchCompatible( Class exception, ObjectType catchType )
     {
 	return true;
 
 	// TODO:   Fix this in BCEL!!!!!
 
 	// NULL means ALL.
 //  	if (catchType == null) return true;
 
 //  	ObjectType excepType = 
 //  	    new ObjectType( exception.getName() );
 
 //  	if (excepType.getSignature().equals( catchType.getSignature() )) 
 //  	    return true;
 //  	return catchType.subclassOf( excepType );
     }
 
     public BlockVertex getStartVertex() {
 	return this.start;
     }
 
     public BlockVertex getEndVertex() {
 	return this.end;
     }
 
     public void setStartVertex(BlockVertex start) {
 	this.start = start;
 	addVertex( start );
     }
 
     public void setEndVertex(BlockVertex end) {
 	this.end = end;
 	addVertex( end );
     }
 
     public int makeNewLocal(String name, Type type) {
 	LocalVariableGen lvg =
 	    method.addLocalVariable( name, type,
 				     method.getInstructionList().getStart(),
 				     method.getInstructionList().getEnd());
 
 	return lvg.getIndex();
     }
 
     public Method getMethod() {
 	BytecodeLayout layout = new BytecodeLayout( method );
 	DFS dfs = new DFS();
 	dfs.visit( this, getStartVertex(), layout );
 
 	//	layout.visit( this, getStartVertex() );
 
 	try {
 	    return layout.getMethod();
 	} catch (QuiltException e) {
 	    System.err.println("Warning:  Instrumentation Failed.");
 	    e.printStackTrace();
 	    return oldMethod;
 	}
     }
 
     public boolean doesHandle( InstructionHandle ih,
 			       CodeExceptionGen handler )
     {
 	InstructionHandle curr = handler.getStartPC();
 
 	if (handler.getEndPC() == ih) return true;
 
 	while ( curr != handler.getEndPC() ) {
 	    if (ih == curr) return true;
 	    curr = curr.getNext();
 	}
 
 	return false;
     }
 
     public String getMethodName() {
 	return method.getName();
     }
 
     public void updateEdge( FlowControlEdge edge ) {
 	if ( getEdges().contains( edge )) {
 	    removeEdge( edge );
 	}
 	addEdge( edge );
     }
 
     public void addEdge( FlowControlEdge edge ) {
 	BlockVertex source = edge.getSource();
 	BlockVertex target = edge.getTarget();
 
 	if (source == null) {
 	    source = getStartVertex();
 	}
 
 	if (target == null) {
 	    target = getEndVertex();
 	}
 	
 	addEdge( edge, source, target );
     }
 
     private void handleNormal( EdgeFactory factory,
 			       InstructionHandle next,
 			       InstructionHandle last,
 			       BlockVertex vertex,
 			       Map blocks,
 			       LocalVariableTable lvt) {
 	BlockVertex target = lookup( blocks, next );
 	if (target == null) System.err.println("Wrong Lookup in handleNormal");
 	FlowControlEdge nEdge = 
 	    factory.makeNormalEdge( vertex, target );
 
 	addEdge( nEdge );
     }
 
     private void handleSelect( EdgeFactory factory,
 			   InstructionHandle next,
 			   InstructionHandle last,
 			   BlockVertex vertex,
 			       Map blocks,
 			       LocalVariableTable lvt) {
 
 	Select instruction = (Select) last.getInstruction();
 	String expr = getStackContents( last, lvt );
 	InstructionHandle targets[] = 
 	    instruction.getTargets();
 	int match[] =
 	    instruction.getMatchs();
 	
 	BlockVertex target;
 	FlowControlEdge sEdge;
 	
 	// CASE . . .
 	for (int i = 0; i < targets.length; i++) {
 	    target = lookup( blocks, targets[i] );
 	    if (target == null) System.err.println("Wrong Lookup in handleSelect(1)");
 	    sEdge = factory.makeSelectEdge( vertex, target, 
 					    expr, match[i] );  
 	    
 	    addEdge( sEdge, vertex, target );
 	}
 	
 	// DEFAULT
 	target = lookup( blocks, instruction.getTarget() );
 	if (target == null) System.err.println("Wrong Lookup in handleSelect(2)");
 
 	sEdge = factory.makeSelectEdge( vertex, target, expr );
 	
 	addEdge( sEdge, vertex, target );
     }
 
     private void handleIf( EdgeFactory factory,
 			   InstructionHandle next,
 			   InstructionHandle last,
 			   BlockVertex vertex,
 			       Map blocks,
 			       LocalVariableTable lvt) {
 			 
 	BlockVertex target;
 	FlowControlEdge bEdge;
 	String expr = getStackContents( last, lvt );
 	IfInstruction ifInst = 
 	    (IfInstruction) last.getInstruction();
 	
 	// THEN
 	target = lookup( blocks, ifInst.getTarget() );
 	if (target == null) System.err.println("Wrong Lookup in handleIf(1)");
 
 	bEdge = factory.makeBranchEdge( vertex, target, expr, true );
 	
 	addEdge( bEdge, vertex, target );
 	
 	// ELSE
 	target = lookup( blocks, next );
 	if (target == null) System.err.println("Wrong Lookup in handleIf(2)");
 
 	bEdge = factory.makeBranchEdge( vertex, target, expr, false );
 	
 	addEdge( bEdge, vertex, target );
     }
     
     private void handleGoto( EdgeFactory factory,
 			     InstructionHandle next,
 			     InstructionHandle last,
 			     BlockVertex vertex,
 			       Map blocks,
 			       LocalVariableTable lvt) {
 			    
 	// Unconditional Jump
 	GotoInstruction goI = (GotoInstruction) last.getInstruction();
 	BlockVertex target = lookup( blocks, goI.getTarget() );
 	if (target == null) System.err.println("Wrong Lookup in handleGoto");
 
 	FlowControlEdge nEdge = 
 	    factory.makeNormalEdge( vertex, target );
 	
 	addEdge( nEdge, vertex, target );
     }
 
     private void handleJSR( EdgeFactory factory,
 			    InstructionHandle next,
 			    InstructionHandle last,
 			    BlockVertex vertex,
 			    Map blocks,
 			    LocalVariableTable lvt) {
        	// SUBROUTINE. . . Don't forget about the RET.
 	JsrInstruction jsrI = (JsrInstruction) last.getInstruction();
 	
 	BlockVertex jsrTarget = lookup( blocks, jsrI.getTarget() );
 	BlockVertex nTarget = lookup( blocks, last.getNext() );
 	
 	FlowControlEdge jEdge = 
 	    factory.makeJSREdge( vertex, jsrTarget );
 	FlowControlEdge nEdge =
 	    factory.makeNormalEdge( vertex, nTarget );
 	
 	addEdge( jEdge, vertex, jsrTarget );
 	addEdge( nEdge, vertex, nTarget );
 	
 	jsrEdges.put( jEdge, nEdge );
     }
 
     private void handleExceptionThrower( EdgeFactory factory,
 					 InstructionHandle next,
 					 InstructionHandle last,
 					 BlockVertex vertex,
 			       Map blocks,
 			       LocalVariableTable lvt) {
 					 
 	BlockVertex target = null;
 	if (last.getInstruction() instanceof InvokeInstruction) {
 	    target = lookup( blocks, next );
 	    if (target == null) System.err.println("Wrong Lookup in handleExceptionThrower(1) -- next: " + next);
 
 	    FlowControlEdge nEdge = factory.makeNormalEdge( vertex,
 							    target );
 	    addEdge( nEdge, vertex, target );
 	    
 	    CodeExceptionGen handlers[] =
 		method.getExceptionHandlers();
 	    
 	    for (int j = 0; j < handlers.length; j++) {
 		if (doesHandle( last, handlers[j] )) {
 		    target = lookup( blocks, handlers[j].getHandlerPC() );
 		    if (target == null) System.err.println("Wrong Lookup in handleExceptionThrower(2) -- handler: " + handlers[j].getHandlerPC() );
 
 		    FlowControlEdge xEdge =
 			factory.makeExceptionEdge( vertex,
 						   target, 
 						   handlers[j].getCatchType());
 		    addEdge( xEdge, vertex, 
 			     lookup( blocks, 
 				     handlers[j].getHandlerPC() ) );
 		}
 	    }
 	}
 	// ATHROW always throws an Exception.  So, don't
 	// create a Normal Edge for it.
 	if (!(last.getInstruction() instanceof ATHROW)) {
 	    target = lookup( blocks, next );
 	    if (target == null) System.err.println("Wrong Lookup in handleExceptionThrower(3) -- next: " + next );
 
 	    FlowControlEdge nEdge = factory.makeNormalEdge( vertex, 
 							    target );
 		    
 	    addEdge(nEdge, vertex, target);
 	}
 		
 	ExceptionThrower inst = 
 	    (ExceptionThrower) last.getInstruction();
 	
 	Class exceptions[] = inst.getExceptions();
 	CodeExceptionGen handlers[] = 
 	    method.getExceptionHandlers();
 	
 	for (int i = 0; i < exceptions.length; i++) {
 	    int numHandlers = 0;
 	    for (int j = 0; j < handlers.length; j++) {
 		if (handlers[j].containsTarget( last )) {
 		    if (isCatchCompatible( exceptions[i],
 					   handlers[j].getCatchType())) {
 			numHandlers ++;
 			FlowControlEdge xEdge =
 			    factory.makeExceptionEdge( vertex,
 						       lookup( blocks, 
 							       handlers[j].getHandlerPC() ), 
 						       exceptions[i] );
 			target = lookup( blocks, handlers[j].getHandlerPC() );
 			if (target == null) System.err.println("Wrong Lookup in handleExceptionHandlers(4) -- handler: " + handlers[j].getHandlerPC() );
 			addEdge( xEdge, vertex, target);
 		    }
 		}
 	    } 
 	    
 //	    if (numHandlers == 0) {
 //		FlowControlEdge xEdge = 
 //		    factory.makeExceptionEdge( vertex,
 //				       exceptions[i]);
 //		addEdge( xEdge, vertex, getEndVertex() );
 //	    }
 	}
     }
 
     public boolean hasInbound( InstructionHandle instructionHandle ) {
 	if (instructionHandle.hasTargeters()) {
 	    InstructionTargeter targeters[] = instructionHandle.getTargeters();
 	    for (int j = 0; j < targeters.length; j++) {
 		if (targeters[j] instanceof BranchInstruction)
 		    return true;
 		if (targeters[j] instanceof CodeExceptionGen)
 		    return true;
 	    }
 	}
 	
 	return false;
     }
 
     public boolean hasOutbound( InstructionHandle instructionHandle ) {
 	Instruction inst = instructionHandle.getInstruction();
 
 	if (inst instanceof BranchInstruction) 
 	    return true;
 	if (inst instanceof ExceptionThrower)
 	    return true;
 	return false;
     }
 
 
 }